<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-hemisu.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="hemisu">










<meta name="description" content="Just do...">
<meta name="keywords" content="web, 前端, 生活, 分享">
<meta property="og:type" content="website">
<meta property="og:title" content="何米酥`s Blog">
<meta property="og:url" content="http://www.hemisu.com/page/9/index.html">
<meta property="og:site_name" content="何米酥`s Blog">
<meta property="og:description" content="Just do...">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="何米酥`s Blog">
<meta name="twitter:description" content="Just do...">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://www.hemisu.com/page/9/">





  <title>何米酥`s Blog</title>
  








  <!-- Hotjar Tracking Code for www.hemisu.com -->
  <script>
      (function(h,o,t,j,a,r){
          h.hj=h.hj||function(){(h.hj.q=h.hj.q||[]).push(arguments)};
          h._hjSettings={hjid:1933736,hjsv:6};
          a=o.getElementsByTagName('head')[0];
          r=o.createElement('script');r.async=1;
          r.src=t+h._hjSettings.hjid+j+h._hjSettings.hjsv;
          a.appendChild(r);
      })(window,document,'https://static.hotjar.com/c/hotjar-','.js?sv=');
  </script>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left 
  page-home">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">何米酥`s Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">EFE</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/22/201/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/22/201/" itemprop="url">PAT A1020</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-22T15:55:05+00:00">
                2017-02-22
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line gives a positive integer N (&lt;=30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.</p>
<p>Sample Input:<br>7<br>2 3 1 5 7 6 4<br>1 2 3 4 5 6 7<br>Sample Output:<br>4 1 6 3 5 7 2<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 50;</span><br><span class="line">struct node&#123;</span><br><span class="line">    int data;</span><br><span class="line">    node* lchild;</span><br><span class="line">    node* rchild;</span><br><span class="line">&#125;;</span><br><span class="line">int pre[maxn], in[maxn], post[maxn];//先序，中序以及后序</span><br><span class="line">int n;//结点个数</span><br><span class="line">//当前二叉树后序序列区间为[postL,postR], 中序序列区间为[inL, inR]</span><br><span class="line">//create函数返回构建出的二叉树的根节点地址</span><br><span class="line">node* create(int postL,int postR, int inL, int inR)&#123;</span><br><span class="line">    if (postL &gt; postR) &#123;</span><br><span class="line">        return NULL;//若后序序列长度小于0，则直接返回</span><br><span class="line">    &#125;</span><br><span class="line">    node* root = new node;//新建一个结点，用来存放当前二叉树的根节点</span><br><span class="line">    root-&gt;data = post[postR];//新结点的数据域为根结点的值</span><br><span class="line">    int k;//k为根节点的值在中序序列中的位置</span><br><span class="line">    for (k = inL; k &lt;= inR; k++) &#123;</span><br><span class="line">        if (in[k] == post[postR]) &#123;//如果在中序序列中找到了</span><br><span class="line">            break;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    int numLeft = k - inL;//左子树的结点个数</span><br><span class="line">    //返回左子树的根结点地址，赋值给root的左指针</span><br><span class="line">    root-&gt;lchild = create(postL, postL + numLeft - 1, inL, k - 1);</span><br><span class="line">    //返回右子树的根节点地址，赋值给root的右指针</span><br><span class="line">    root-&gt;rchild = create(postL + numLeft, postR - 1, k + 1, inR);</span><br><span class="line">    return root;</span><br><span class="line">&#125;</span><br><span class="line">int num = 0;//已输出的结点个数</span><br><span class="line">void BFS(node* root)&#123;</span><br><span class="line">    queue&lt;node*&gt; q;//注意队列里面储存的是地址</span><br><span class="line">    q.push(root);//将根节点地址入队</span><br><span class="line">    while (!q.empty()) &#123;</span><br><span class="line">        node* now = q.front();//取出队首元素</span><br><span class="line">        q.pop();</span><br><span class="line">        printf(&quot;%d&quot;, now-&gt;data);//打印队首元素</span><br><span class="line">        num++;</span><br><span class="line">        if (num &lt; n) printf(&quot; &quot;);</span><br><span class="line">        if (now-&gt;lchild != NULL) q.push(now-&gt;lchild);</span><br><span class="line">        if (now-&gt;rchild != NULL) q.push(now-&gt;rchild);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;post[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;in[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    node* root = create(0, n - 1, 0, n - 1);//建树</span><br><span class="line">    BFS(root);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/22/200/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/22/200/" itemprop="url">PAT A1091</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-22T13:27:08+00:00">
                2017-02-22
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>One important factor to identify acute stroke (急性脑卒中) is the volume of the stroke core. Given the results of image analysis in which the core regions are identified in each MRI slice, your job is to calculate the volume of the stroke core.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains 4 positive integers: M, N, L and T, where M and N are the sizes of each slice (i.e. pixels of a slice are in an M by N matrix, and the maximum resolution is 1286 by 128); L (&lt;=60) is the number of slices of a brain; and T is the integer threshold (i.e. if the volume of a connected core is less than T, then that core must not be counted).</p>
<p>Then L slices are given. Each slice is represented by an M by N matrix of 0’s and 1’s, where 1 represents a pixel of stroke, and 0 means normal. Since the thickness of a slice is a constant, we only have to count the number of 1’s to obtain the volume. However, there might be several separated core regions in a brain, and only those with their volumes no less than T are counted. Two pixels are “connected” and hence belong to the same region if they share a common side, as shown by Figure 1 where all the 6 red pixels are connected to the blue one.</p>
<p><img src="https://www.patest.cn/upload/g0_nf8qpnrr0f1.jpg" alt="请输入图片描述"><br>Figure 1<br>Output Specification:</p>
<p>For each case, output in a line the total volume of the stroke core.</p>
<p>Sample Input:<br>3 4 5 2<br>1 1 1 1<br>1 1 1 1<br>1 1 1 1<br>0 0 1 1<br>0 0 1 1<br>0 0 1 1<br>1 0 1 1<br>0 1 0 0<br>0 0 0 0<br>1 0 1 1<br>0 0 0 0<br>0 0 0 0<br>0 0 0 1<br>0 0 0 1<br>1 0 0 0<br>Sample Output:<br>26<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">struct Node&#123;</span><br><span class="line">    int x, y, z;//位置(x, y, z)</span><br><span class="line">&#125; node;</span><br><span class="line">int n, m, slice, T;//矩阵为n*m,共有slice层，T为卒中核心区1的个数的下限</span><br><span class="line">int pixel[1290][130][61];//三维01矩阵</span><br><span class="line">bool inq[1290][130][61] = &#123;false&#125;;//记录位置(x, y, z)是否入过队</span><br><span class="line">int X[6] = &#123;0, 0, 0, 0, 1, -1&#125;;</span><br><span class="line">int Y[6] = &#123;0, 0, 1, -1, 0, 0&#125;;</span><br><span class="line">int Z[6] = &#123;1, -1, 0, 0, 0, 0&#125;;</span><br><span class="line"></span><br><span class="line">bool Judge(int x, int y, int z)&#123;//判断(x, y, z)是否需要访问</span><br><span class="line">    //越界返回false</span><br><span class="line">    if (x &gt;= n || x &lt; 0 || y &gt;= m || y &lt; 0 || z &gt;= slice || z &lt; 0) return false;</span><br><span class="line">    //若当前位置为0或者已经入过队,则返回false</span><br><span class="line">    if (pixel[x][y][z] == 0 ||inq[x][y][z] == true) return false;</span><br><span class="line">    //以上都不满足，返回true</span><br><span class="line">    return true;</span><br><span class="line">&#125;</span><br><span class="line">//bfs函数访问位置(x, y, z)所在的块，将该块中所有&quot;1&quot;的inq都设置为true</span><br><span class="line">int BFS(int x, int y, int z)&#123;</span><br><span class="line">    int tot = 0;//当前块中1的个数</span><br><span class="line">    queue&lt;Node&gt; Q;//将结点node入队</span><br><span class="line">    node.x = x, node.y = y, node.z = z;//结点node的位置为(x, y, z)</span><br><span class="line">    Q.push(node);//将结点node入队</span><br><span class="line">    inq[x][y][z] = true;//设置位置(x, y, z)已入过队</span><br><span class="line">    while (!Q.empty()) &#123;</span><br><span class="line">        Node top = Q.front();//取出队首元素</span><br><span class="line">        Q.pop();//队首出队</span><br><span class="line">        tot++;</span><br><span class="line">        for (int i = 0; i &lt; 6; i++) &#123;//循环6次，得到6个方向</span><br><span class="line">            int newX = top.x + X[i];</span><br><span class="line">            int newY = top.y + Y[i];</span><br><span class="line">            int newZ = top.z + Z[i];</span><br><span class="line">            if(Judge(newX, newY, newZ))&#123;//新位置(newX, newY, newZ)需要访问</span><br><span class="line">                //设置node坐标</span><br><span class="line">                node.x = newX, node.y = newY, node.z = newZ;</span><br><span class="line">                Q.push(node);//将结点node入队</span><br><span class="line">                inq[newX][newY][newZ] = true;//设置(newX, newY, newZ)已入过队</span><br><span class="line">                </span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    if (tot &gt;= T) &#123;</span><br><span class="line">        return tot;</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        return 0;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%d%d%d&quot;, &amp;n, &amp;m, &amp;slice, &amp;T);</span><br><span class="line">    for (int z = 0; z &lt; slice; z++) &#123;</span><br><span class="line">        for (int x = 0; x &lt; n; x++) &#123;</span><br><span class="line">            for (int y = 0; y &lt; m; y++) &#123;</span><br><span class="line">                scanf(&quot;%d&quot;, &amp;pixel[x][y][z]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    int ans = 0;//记录卒中核心区中1的个数总和</span><br><span class="line">    for (int z = 0; z &lt; slice; z++) &#123;</span><br><span class="line">        for (int x = 0; x &lt; n; x++) &#123;</span><br><span class="line">            for (int y = 0; y &lt; m; y++) &#123;</span><br><span class="line">                //如果当前位置为1，且未被访问，则BFS当前块</span><br><span class="line">                if (pixel[x][y][z] == 1 &amp;&amp; inq[x][y][z] == false) &#123;</span><br><span class="line">                    ans += BFS(x, y, z);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%d\n&quot;, ans);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/22/199/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/22/199/" itemprop="url">PAT A1103</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-22T11:04:28+00:00">
                2017-02-22
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>The K-P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K-P factorization of N for any positive integers N, K and P.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case which gives in a line the three positive integers N (&lt;=400), K (&lt;=N) and P (1&lt;P&lt;=7). The numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each case, if the solution exists, output in the format:</p>
<p>N = n1^P + … nK^P</p>
<p>where ni (i=1, … K) is the i-th factor. All the factors must be printed in non-increasing order.</p>
<p>Note: the solution may not be unique. For example, the 5-2 factorization of 169 has 9 solutions, such as 122 + 42 + 22 + 22 + 12, or 112 + 62 + 22 + 22 + 22, or more. You must output the one with the maximum sum of the factors. If there is a tie, the largest factor sequence must be chosen – sequence { a1, a2, … aK } is said to be larger than { b1, b2, … bK } if there exists 1&lt;=L&lt;=K such that ai=bi for i<l and al>bL</l></p>
<p>If there is no solution, simple output “Impossible”.</p>
<p>Sample Input 1:<br>169 5 2<br>Sample Output 1:<br>169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2<br>Sample Input 2:<br>169 167 3<br>Sample Output 2:<br>Impossible<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">//#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">//n, k, p如题所述，maxFacSum记录最大底数之和</span><br><span class="line">int n, k, p, maxFacsum = -1;</span><br><span class="line">//fac记录了0^p, 1^p...i^p ,使i^p为不超过n的最大数</span><br><span class="line">//ans存放最优底数列,temp存放递归中的临时底数数列</span><br><span class="line">vector&lt;int&gt; fac, ans, temp;</span><br><span class="line">//power 函数计算x^p</span><br><span class="line">int power(int x)&#123;</span><br><span class="line">    int ans = 1;</span><br><span class="line">    for (int i = 0; i &lt; p; i++) &#123;</span><br><span class="line">        ans *= x;</span><br><span class="line">    &#125;</span><br><span class="line">    return ans;</span><br><span class="line">&#125;</span><br><span class="line">//init函数预处理fac数组，注意把0也存进去</span><br><span class="line">void init()&#123;</span><br><span class="line">    int i = 0, temp = 0;</span><br><span class="line">    while (temp &lt;= n) &#123;//当i^p没有超过n时，不断把i^p加入fac</span><br><span class="line">        fac.push_back(temp);</span><br><span class="line">        temp = power(++i);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">//dfs函数，当前访问fac[index], nowK为当前选中个数</span><br><span class="line">//sum为当前选中数之和，facSum为当前选中底数之和</span><br><span class="line">void DFS(int index, int nowK, int sum, int facSum)&#123;</span><br><span class="line">    if (sum == n &amp;&amp; nowK == k) &#123;//找到一个满足的序列</span><br><span class="line">        if (facSum &gt; maxFacsum) &#123;//如果底数之和更大</span><br><span class="line">            ans = temp;</span><br><span class="line">            maxFacsum = facSum;</span><br><span class="line">        &#125;</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    if (sum &gt; n || nowK &gt; k) return;//这种情况不会产生答案，直接返回</span><br><span class="line">    if(index - 1 &gt;= 0)&#123;//fac[0]不需要选择</span><br><span class="line">        temp.push_back(index);//把底数index加入临时序列temp</span><br><span class="line">        DFS(index, nowK + 1, sum + fac[index], facSum + index);//&quot;选&quot;的分支</span><br><span class="line">        temp.pop_back();//&quot;选&quot;的分支结束后把刚加进去的数pop掉</span><br><span class="line">        DFS(index - 1, nowK, sum, facSum);//&quot;不选&quot;的分支</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%d%d&quot;, &amp;n, &amp;k, &amp;p);</span><br><span class="line">    init();//初始化fac数组</span><br><span class="line">    DFS(fac.size() - 1, 0, 0, 0);//从fac的最后一位开始往前搜索</span><br><span class="line">    if (maxFacsum == -1) &#123;</span><br><span class="line">        printf(&quot;Impossible\n&quot;);</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        printf(&quot;%d = %d^%d&quot;, n, ans[0], p);//输出ans结果</span><br><span class="line">        for (int i = 1; i &lt; ans.size(); i++) &#123;</span><br><span class="line">            printf(&quot; + %d^%d&quot;, ans[i], p);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/21/197/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/21/197/" itemprop="url">PAT A1097</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-21T16:09:00+00:00">
                2017-02-21
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Given a singly linked list L with integer keys, you are supposed to remove the nodes with duplicated absolute values of the keys. That is, for each value K, only the first node of which the value or absolute value of its key equals K will be kept. At the mean time, all the removed nodes must be kept in a separate list. For example, given L being 21→-15→-15→-7→15, you must output 21→-15→-7, and the removed list -15→15.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains the address of the first node, and a positive N (&lt;= 105) which is the total number of nodes. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.</p>
<p>Then N lines follow, each describes a node in the format:</p>
<p>Address Key Next</p>
<p>where Address is the position of the node, Key is an integer of which absolute value is no more than 104, and Next is the position of the next node.</p>
<p>Output Specification:</p>
<p>For each case, output the resulting linked list first, then the removed list. Each node occupies a line, and is printed in the same format as in the input.</p>
<p>Sample Input:<br>00100 5<br>99999 -7 87654<br>23854 -15 00000<br>87654 15 -1<br>00000 -15 99999<br>00100 21 23854<br>Sample Output:<br>00100 21 23854<br>23854 -15 99999<br>99999 -7 -1<br>00000 -15 87654<br>87654 15 -1<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">//#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 100005;</span><br><span class="line">const int TABLE = 100010;</span><br><span class="line">struct NODE&#123;</span><br><span class="line">    int address, data, next;</span><br><span class="line">&#125;node[maxn];</span><br><span class="line">bool isExist[TABLE] = &#123;false&#125;;//绝对值是否已经出现</span><br><span class="line">vector&lt;NODE&gt; list1,list2;//没被删除和被删除</span><br><span class="line">int main()&#123;</span><br><span class="line">    fill(isExist, isExist + TABLE, false);//初始化isExist为未出现</span><br><span class="line">//    memset(isExist, false, sizeof(isExist));</span><br><span class="line">    int n, begin, address;</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;begin, &amp;n);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;,&amp;address);</span><br><span class="line">        scanf(&quot;%d%d&quot;, &amp;node[address].data, &amp;node[address].next);</span><br><span class="line">        node[address].address = address;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    for (int p = begin; p != -1; p = node[p].next) &#123;</span><br><span class="line">        if (isExist[abs(node[p].data)] == false) &#123;//不存在</span><br><span class="line">            isExist[abs(node[p].data)] = true;</span><br><span class="line">            list1.push_back(node[p]);</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            list2.push_back(node[p]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    //输出未删除的</span><br><span class="line">    for (int i = 0; i &lt; list1.size(); i++) &#123;</span><br><span class="line">        if (i &lt; list1.size() - 1) &#123;</span><br><span class="line">            printf(&quot;%05d %d %05d\n&quot;, list1[i].address, list1[i].data, list1[i+1].address);</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            printf(&quot;%05d %d -1\n&quot;, list1[i].address, list1[i].data);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    //输出被删除的</span><br><span class="line">    for (int i = 0; i &lt; list2.size(); i++) &#123;</span><br><span class="line">        if (i &lt; list2.size() - 1) &#123;</span><br><span class="line">            printf(&quot;%05d %d %05d\n&quot;, list2[i].address, list2[i].data, list2[i+1].address);</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            printf(&quot;%05d %d -1\n&quot;, list2[i].address, list2[i].data);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>书上答案，思路巧妙，用每个结点加一个order，用maxn，2*maxn将静态链表分为 未删除的结点，删除的结点，无效结点<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">//#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 100005;</span><br><span class="line">const int TABLE = 100010;</span><br><span class="line">struct NODE&#123;</span><br><span class="line">    int address, data, next;</span><br><span class="line">    int order;</span><br><span class="line">&#125;node[maxn];</span><br><span class="line">bool isExist[TABLE] = &#123;false&#125;;//绝对值是否已经出现</span><br><span class="line">bool cmp(NODE a, NODE b)&#123;</span><br><span class="line">    return a.order &lt; b.order;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    fill(isExist, isExist + TABLE, false);//初始化isExist为未出现</span><br><span class="line">//    memset(isExist, false, sizeof(isExist));</span><br><span class="line">    for (int i = 0; i &lt; maxn; i++) &#123;</span><br><span class="line">        node[i].order = 2 * maxn;</span><br><span class="line">    &#125;</span><br><span class="line">    int n, begin, address;</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;begin, &amp;n);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;,&amp;address);</span><br><span class="line">        scanf(&quot;%d%d&quot;, &amp;node[address].data, &amp;node[address].next);</span><br><span class="line">        node[address].address = address;</span><br><span class="line">    &#125;</span><br><span class="line">    int countValid = 0, countRemoved = 0, p = begin;</span><br><span class="line">    while (p != -1)&#123;</span><br><span class="line">        if (isExist[abs(node[p].data)] == false) &#123;//data绝对值不存在</span><br><span class="line">            isExist[abs(node[p].data)] = true;</span><br><span class="line">            node[p].order = countValid++;</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            node[p].order = maxn + countRemoved++;</span><br><span class="line">        &#125;</span><br><span class="line">        p = node[p].next;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    sort(node, node+maxn, cmp);</span><br><span class="line">    int count = countValid + countRemoved;</span><br><span class="line">    for (int i = 0; i &lt; count; i++) &#123;</span><br><span class="line">        if (i != countValid -1 &amp;&amp; i != count -1) &#123;</span><br><span class="line">            printf(&quot;%05d %d %05d\n&quot;, node[i].address, node[i].data, node[i + 1].address);</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            printf(&quot;%05d %d -1\n&quot;, node[i].address, node[i].data);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/21/196/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/21/196/" itemprop="url">PAT B1025/A1074</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-21T14:35:30+00:00">
                2017-02-21
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K = 3, then you must output 3→2→1→6→5→4; if K = 4, you must output 4→3→2→1→5→6.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (&lt;= 105) which is the total number of nodes, and a positive K (&lt;=N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.</p>
<p>Then N lines follow, each describes a node in the format:</p>
<p>Address Data Next</p>
<p>where Address is the position of the node, Data is an integer, and Next is the position of the next node.</p>
<p>Output Specification:</p>
<p>For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.</p>
<p>Sample Input:<br>00100 6 4<br>00000 4 99999<br>00100 1 12309<br>68237 6 -1<br>33218 3 00000<br>99999 5 68237<br>12309 2 33218<br>Sample Output:<br>00000 4 33218<br>33218 3 12309<br>12309 2 00100<br>00100 1 99999<br>99999 5 68237<br>68237 6 -1</p>
<p>给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为1→2→3→4→5→6，K为3，则输出应该为3→2→1→6→5→4；如果K为4，则输出应该为4→3→2→1→5→6，即最后不到K个元素不反转。</p>
<p>输入格式：</p>
<p>每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(&lt;= 105)、以及正整数K(&lt;=N)，即要求反转的子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。</p>
<p>接下来有N行，每行格式为：</p>
<p>Address Data Next</p>
<p>其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。</p>
<p>输出格式：</p>
<p>对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。</p>
<p>输入样例：<br>00100 6 4<br>00000 4 99999<br>00100 1 12309<br>68237 6 -1<br>33218 3 00000<br>99999 5 68237<br>12309 2 33218<br>输出样例：<br>00000 4 33218<br>33218 3 12309<br>12309 2 00100<br>00100 1 99999<br>99999 5 68237<br>68237 6 -1<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">#include &quot;stdlib.h&quot;</span><br><span class="line">//#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 100010;</span><br><span class="line">struct Node&#123;</span><br><span class="line">    int address, data, next;</span><br><span class="line">    int order;//结点在链表上的序号，无效结点记为maxn</span><br><span class="line">&#125;node[maxn];</span><br><span class="line">bool cmp(Node a, Node b)&#123;</span><br><span class="line">    if (a.order == -1 || b.order == -1) &#123;</span><br><span class="line">        return a.order &gt; b.order;</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        return a.order &lt; b.order;</span><br><span class="line">    &#125;//按order从小到大排序</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    for (int i = 0; i &lt; maxn; i++) &#123;</span><br><span class="line">        node[i].order = -1;//初始化全部为无效结点</span><br><span class="line">    &#125;</span><br><span class="line">    int begin, n, K, address;</span><br><span class="line">    scanf(&quot;%d%d%d&quot;, &amp;begin, &amp;n, &amp;K);//起始地址、结点个数、步长</span><br><span class="line">    for (int i = 0; i &lt; n ; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;address);</span><br><span class="line">        scanf(&quot;%d%d&quot;, &amp;node[address].data, &amp;node[address].next);</span><br><span class="line">        node[address].address = address;</span><br><span class="line">    &#125;</span><br><span class="line">    int p = begin, count = 0;//count计数有效结点的数目</span><br><span class="line">    while (p != -1) &#123;</span><br><span class="line">        node[p].order = count++;//结点在单链表中的序号</span><br><span class="line">        p = node[p].next;//下一个结点</span><br><span class="line">    &#125;</span><br><span class="line">    sort(node, node + maxn, cmp);//按单链表从头到尾顺序排列</span><br><span class="line">    //有效结点为前count个结点，为了下面书写方便，因此把count赋值给n</span><br><span class="line">    n = count;</span><br><span class="line">    //单链表已经形成，下面是按题目要求的输出</span><br><span class="line">    for (int i = 0; i &lt; n / K; i++) &#123;//枚举完整的n/K块</span><br><span class="line">        for (int j = (i + 1) * K - 1; j &gt; i * K; j--) &#123;//第i块倒着输出</span><br><span class="line">            printf(&quot;%05d %d %05d\n&quot;, node[j].address,node[j].data,node[j-1].address);</span><br><span class="line">        &#125;</span><br><span class="line">        //下面是每一块最后一个结点的next地址的处理</span><br><span class="line">        printf(&quot;%05d %d &quot;, node[i*K].address, node[i*K].data);</span><br><span class="line">        if (i &lt; n/K -1) &#123;//如果不是最后一块，就指向下一块的最后一个结点</span><br><span class="line">            printf(&quot;%05d\n&quot;, node[(i + 2)*K -1].address);</span><br><span class="line">        &#125;else&#123;//是最后一块时</span><br><span class="line">            if (n%K == 0) &#123;//恰好是最后一个结点，输出-1</span><br><span class="line">                printf(&quot;-1\n&quot;);</span><br><span class="line">            &#125;else&#123;//剩下不完整的块按原先的顺序输出</span><br><span class="line">                printf(&quot;%05d\n&quot;, node[(i+1)*K].address);</span><br><span class="line">                for (int i = n/K * K; i &lt; n; i++) &#123;</span><br><span class="line">                    printf(&quot;%05d %d &quot;, node[i].address, node[i].data);</span><br><span class="line">                    if (i &lt; n - 1) &#123;</span><br><span class="line">                        printf(&quot;%05d\n&quot;, node[i + 1].address);</span><br><span class="line">                    &#125;else&#123;</span><br><span class="line">                        printf(&quot;-1\n&quot;);</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/21/195/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/21/195/" itemprop="url">PAT A1056</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-21T13:46:00+00:00">
                2017-02-21
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Mice and Rice is the name of a programming contest in which each programmer must write a piece of code to control the movements of a mouse in a given map. The goal of each mouse is to eat as much rice as possible in order to become a FatMouse.</p>
<p>First the playing order is randomly decided for NP programmers. Then every NG programmers are grouped in a match. The fattest mouse in a group wins and enters the next turn. All the losers in this turn are ranked the same. Every NG winners are then grouped in the next match until a final winner is determined.</p>
<p>For the sake of simplicity, assume that the weight of each mouse is fixed once the programmer submits his/her code. Given the weights of all the mice and the initial playing order, you are supposed to output the ranks for the programmers.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains 2 positive integers: NP and NG (&lt;= 1000), the number of programmers and the maximum number of mice in a group, respectively. If there are less than NG mice at the end of the player’s list, then all the mice left will be put into the last group. The second line contains NP distinct non-negative numbers Wi (i=0,…NP-1) where each Wi is the weight of the i-th mouse respectively. The third line gives the initial playing order which is a permutation of 0,…NP-1 (assume that the programmers are numbered from 0 to NP-1). All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, print the final ranks in a line. The i-th number is the rank of the i-th programmer, and all the numbers must be separated by a space, with no extra space at the end of the line.</p>
<p>Sample Input:<br>11 3<br>25 18 0 46 37 3 19 22 57 56 10<br>6 0 8 7 10 5 9 1 4 2 3<br>Sample Output:<br>5 5 5 2 5 5 5 3 1 3 5</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">#include &quot;stdlib.h&quot;</span><br><span class="line">//#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 1010;</span><br><span class="line">struct mouse&#123;</span><br><span class="line">    //老鼠</span><br><span class="line">    int weight;//质量</span><br><span class="line">    int R;//排名</span><br><span class="line">&#125;mouse[maxn];</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    int np, ng, order;</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;np, &amp;ng);//number of problem 、 number of group</span><br><span class="line">    for (int i = 0; i &lt; np; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;mouse[i].weight);</span><br><span class="line">    &#125;</span><br><span class="line">    queue&lt;int&gt;  q;//定义一个队列</span><br><span class="line">    for (int i = 0; i &lt; np; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;order);//题目给出的顺序</span><br><span class="line">        q.push(order);//按顺序把老鼠们的标号入队</span><br><span class="line">    &#125;</span><br><span class="line">    int temp = np, group;//temp为当前轮的比赛总老鼠数，group为组数</span><br><span class="line">    while (q.size() != 1) &#123;</span><br><span class="line">        //计算group， 即当前轮分为几组进行比赛</span><br><span class="line">        if (temp % ng == 0) group = temp / ng;</span><br><span class="line">        else group = temp / ng + 1;</span><br><span class="line">        //枚举每一组，选出该组中老鼠质量最大的</span><br><span class="line">        for (int i = 0; i &lt; group ; i++) &#123;</span><br><span class="line">            int k = q.front();//k存放该组质量最大的老鼠的编号</span><br><span class="line">            for (int j = 0; j &lt; ng; j++)&#123;</span><br><span class="line">                //在最后一组老鼠数不足NG时起作用，退出循环</span><br><span class="line">                if (i * ng + j &gt;= temp) &#123;</span><br><span class="line">                    break;</span><br><span class="line">                &#125;</span><br><span class="line">                int front = q.front();</span><br><span class="line">                if (mouse[front].weight &gt; mouse[k].weight) &#123;</span><br><span class="line">                    k = front;//找出质量最大的老鼠</span><br><span class="line">                &#125;</span><br><span class="line">                mouse[front].R = group + 1;//该轮老鼠的排名为group+1</span><br><span class="line">                q.pop();</span><br><span class="line">            &#125;</span><br><span class="line">            q.push(k);</span><br><span class="line">        &#125;</span><br><span class="line">        temp = group; //group只老鼠晋级，因此下轮总老鼠数为gruop</span><br><span class="line">    &#125;</span><br><span class="line">    mouse[q.front()].R = 1;//当队列中只剩1只老鼠时，令其排名为1</span><br><span class="line">    //输出所有老鼠的信息</span><br><span class="line">    for (int i = 0; i &lt; np; i++) &#123;</span><br><span class="line">        printf(&quot;%d&quot;, mouse[i].R);</span><br><span class="line">        if (i &lt; np - 1) &#123;</span><br><span class="line">            printf(&quot; &quot;);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/21/194/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/21/194/" itemprop="url">PAT A1051</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-21T11:05:21+00:00">
                2017-02-21
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.</p>
<p>Sample Input:<br>5 7 5<br>1 2 3 4 5 6 7<br>3 2 1 7 5 6 4<br>7 6 5 4 3 2 1<br>5 6 4 3 7 2 1<br>1 7 6 5 4 3 2<br>Sample Output:<br>YES<br>NO<br>NO<br>YES<br>NO</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">#include &quot;stdlib.h&quot;</span><br><span class="line">//#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">#include &quot;stack&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 1010;</span><br><span class="line">int arr[maxn];//保存题目给定的出栈序列</span><br><span class="line">stack&lt;int&gt; st;//定义栈st 用以存放int型元素</span><br><span class="line">int main()&#123;</span><br><span class="line">    int m, n, T;</span><br><span class="line">    scanf(&quot;%d%d%d&quot;, &amp;m, &amp;n, &amp;T);</span><br><span class="line">    while (T--) &#123;</span><br><span class="line">        while (!st.empty()) &#123;//清空栈</span><br><span class="line">            st.pop();</span><br><span class="line">        &#125;</span><br><span class="line">        for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;arr[i]);</span><br><span class="line">        &#125;</span><br><span class="line">        int current = 1;//指向出栈序列中的待出栈元素</span><br><span class="line">        bool flag = true;</span><br><span class="line">        for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">            st.push(i);//把i压入栈</span><br><span class="line">            if (st.size() &gt; m) &#123;//如果此时栈中元素大于容量m，则序列非法</span><br><span class="line">                flag = false;</span><br><span class="line">                break;</span><br><span class="line">            &#125;</span><br><span class="line">            //栈顶元素与出栈序列当前位置的元素相同时</span><br><span class="line">            while (!st.empty() &amp;&amp; st.top() == arr[current]) &#123;</span><br><span class="line">                st.pop();//反复弹栈并令current++</span><br><span class="line">                current++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        if (st.empty() == true &amp;&amp; flag == true) &#123;</span><br><span class="line">            printf(&quot;YES\n&quot;);</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            printf(&quot;NO\n&quot;);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/21/192/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/21/192/" itemprop="url">PAT A1052</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-21T10:16:00+00:00">
                2017-02-21
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains a positive N (&lt; 105) and an address of the head node, where N is the total number of nodes in memory and the address of a node is a 5-digit positive integer. NULL is represented by -1.</p>
<p>Then N lines follow, each describes a node in the format:</p>
<p>Address Key Next</p>
<p>where Address is the address of the node in memory, Key is an integer in [-105, 105], and Next is the address of the next node. It is guaranteed that all the keys are distinct and there is no cycle in the linked list starting from the head node.</p>
<p>Output Specification:</p>
<p>For each test case, the output format is the same as that of the input, where N is the total number of nodes in the list and all the nodes must be sorted order.</p>
<p>Sample Input:<br>5 00001<br>11111 100 -1<br>00001 0 22222<br>33333 100000 11111<br>12345 -1 33333<br>22222 1000 12345<br>Sample Output:<br>5 12345<br>12345 -1 00001<br>00001 0 11111<br>11111 100 22222<br>22222 1000 33333<br>33333 100000 -1<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">#include &quot;stdlib.h&quot;</span><br><span class="line">//#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 100010;</span><br><span class="line">struct NODE&#123;</span><br><span class="line">    int next, data, address;</span><br><span class="line">    bool flag;//结点在链表中是否出现</span><br><span class="line">&#125;node[maxn];</span><br><span class="line"></span><br><span class="line">bool cmp(NODE a, NODE b)&#123;</span><br><span class="line">    if (a.flag == false || b.flag == false) &#123;</span><br><span class="line">        return a.flag &gt; b.flag;</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        return a.data &lt; b.data;//递增排序</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    for (int i = 0; i &lt; maxn; i++) &#123;</span><br><span class="line">        node[i].flag = false;//没有在第一条链表出现</span><br><span class="line">    &#125;</span><br><span class="line">    int n, begin, count = 0;//s1,s2分别代表两条链表的首地址</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;n, &amp;begin);</span><br><span class="line">    int address;//结点地址与下一结点地址</span><br><span class="line">    for (int i = 0 ; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;address);</span><br><span class="line">        scanf(&quot;%d%d&quot;, &amp;node[address].data, &amp;node[address].next);</span><br><span class="line">        node[address].address = address;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int p = begin; p != -1; p = node[p].next) &#123;</span><br><span class="line">        node[p].flag = true;//枚举第一条链表的所有结点，令其出现次数为1</span><br><span class="line">        count++;</span><br><span class="line">    &#125;</span><br><span class="line">    if (count == 0) &#123;</span><br><span class="line">        printf(&quot;0 -1&quot;);//特判，新链表中没有结点时输出0 -1</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        sort(node, node + maxn, cmp);</span><br><span class="line">        printf(&quot;%d %05d\n&quot;, count, node[0].address);</span><br><span class="line">        for (int i = 0; i &lt; count; i++) &#123;</span><br><span class="line">            if (i != count - 1) &#123;</span><br><span class="line">                printf(&quot;%05d %d %05d\n&quot;, node[i].address, node[i].data, node[i+1].address);</span><br><span class="line">            &#125;else&#123;</span><br><span class="line">                printf(&quot;%05d %d -1\n&quot;,node[i].address, node[i].data);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<ul>
<li>链表的题最好画一下</li>
<li>这题排序后，地址也变动，所以需要记录各个结点自己的地址，在输出的时候，输出自己的地址和下一个结点的地址（而不是本结点的next）</li>
<li>输出地址的时候要注意，-1不能使用%05d输出，否则会输出-0001（而不是-1或者-00001），因此必须要留意-1的输出。</li>
<li>数据里面还有均为无效的情况，这是就要根据有效结点的个数特判输出”0 -1”</li>
</ul>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/21/191/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/21/191/" itemprop="url">PAT A1032</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-21T09:50:57+00:00">
                2017-02-21
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, “loading” and “being” are stored as showed in Figure 1.<br><img src="https://www.patest.cn/upload/1w_m16pjsommxz.jpg" alt="请输入图片描述"></p>
<p>Figure 1<br>You are supposed to find the starting position of the common suffix (e.g. the position of “i” in Figure 1).</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive N (&lt;= 105), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by -1.</p>
<p>Then N lines follow, each describes a node in the format:</p>
<p>Address Data Next</p>
<p>where Address is the position of the node, Data is the letter contained by this node which is an English letter chosen from {a-z, A-Z}, and Next is the position of the next node.</p>
<p>Output Specification:</p>
<p>For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output “-1” instead.</p>
<p>Sample Input 1:<br>11111 22222 9<br>67890 i 00002<br>00010 a 12345<br>00003 g -1<br>12345 D 67890<br>00002 n 00003<br>22222 B 23456<br>11111 L 00001<br>23456 e 67890<br>00001 o 00010<br>Sample Output 1:<br>67890<br>Sample Input 2:<br>00001 00002 4<br>00001 a 10001<br>10001 s -1<br>00002 a 10002<br>10002 t -1<br>Sample Output 2:<br>-1</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">#include &quot;stdlib.h&quot;</span><br><span class="line">//#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;algorithm&quot;</span><br><span class="line">//using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 100010;</span><br><span class="line">struct NODE&#123;</span><br><span class="line">    char data;//数据域</span><br><span class="line">    int next;//指针域</span><br><span class="line">    bool flag;//结点是否在第一条链表中出现</span><br><span class="line">&#125;node[maxn];</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    for (int i = 0; i &lt; maxn; i++) &#123;</span><br><span class="line">        node[i].flag = false;//没有在第一条链表出现</span><br><span class="line">    &#125;</span><br><span class="line">    int s1, s2,n;//s1,s2分别代表两条链表的首地址</span><br><span class="line">    scanf(&quot;%d%d%d&quot;, &amp;s1, &amp;s2, &amp;n);</span><br><span class="line">    int address, next;//结点地址与下一结点地址</span><br><span class="line">    char data;//数据</span><br><span class="line">    for (int i = 0 ; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d %c %d&quot;, &amp;address, &amp;data, &amp;next);</span><br><span class="line">        node[address].data = data;</span><br><span class="line">        node[address].next = next;</span><br><span class="line">    &#125;</span><br><span class="line">    int p;</span><br><span class="line">    for (p = s1; p != -1; p = node[p].next) &#123;</span><br><span class="line">        node[p].flag = true;//枚举第一条链表的所有结点，令其出现次数为1</span><br><span class="line">    &#125;</span><br><span class="line">    for (p = s2; p != -1; p = node[p].next) &#123;</span><br><span class="line">        //找到第一个已经在第一条链表中出现的结点</span><br><span class="line">        if (node[p].flag == true) &#123;</span><br><span class="line">            break;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    if (p != -1) &#123;</span><br><span class="line">        printf(&quot;%05d\n&quot;, p);</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        printf(&quot;-1\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/20/187/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/20/187/" itemprop="url">PAT A1022</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-20T14:32:00+00:00">
                2017-02-20
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>A Digital Library contains millions of books, stored according to their titles, authors, key words of their abstracts, publishers, and published years. Each book is assigned an unique 7-digit number as its ID. Given any query from a reader, you are supposed to output the resulting books, sorted in increasing order of their ID’s.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains a positive integer N (&lt;=10000) which is the total number of books. Then N blocks follow, each contains the information of a book in 6 lines:</p>
<p>Line #1: the 7-digit ID number;<br>Line #2: the book title – a string of no more than 80 characters;<br>Line #3: the author – a string of no more than 80 characters;<br>Line #4: the key words – each word is a string of no more than 10 characters without any white space, and the keywords are separated by exactly one space;<br>Line #5: the publisher – a string of no more than 80 characters;<br>Line #6: the published year – a 4-digit number which is in the range [1000, 3000].<br>It is assumed that each book belongs to one author only, and contains no more than 5 key words; there are no more than 1000 distinct key words in total; and there are no more than 1000 distinct publishers.</p>
<p>After the book information, there is a line containing a positive integer M (&lt;=1000) which is the number of user’s search queries. Then M lines follow, each in one of the formats shown below:</p>
<p>1: a book title<br>2: name of an author<br>3: a key word<br>4: name of a publisher<br>5: a 4-digit number representing the year<br>Output Specification:</p>
<p>For each query, first print the original query in a line, then output the resulting book ID’s in increasing order, each occupying a line. If no book is found, print “Not Found” instead.</p>
<p>Sample Input:<br>3<br>1111111<br>The Testing Book<br>Yue Chen<br>test code debug sort keywords<br>ZUCS Print<br>2011<br>3333333<br>Another Testing Book<br>Yue Chen<br>test code sort keywords<br>ZUCS Print2<br>2012<br>2222222<br>The Testing Book<br>CYLL<br>keywords debug book<br>ZUCS Print2<br>2011<br>6<br>1: The Testing Book<br>2: Yue Chen<br>3: keywords<br>4: ZUCS Print<br>5: 2011<br>3: blablabla<br>Sample Output:<br>1: The Testing Book<br>1111111<br>2222222<br>2: Yue Chen<br>1111111<br>3333333<br>3: keywords<br>1111111<br>2222222<br>3333333<br>4: ZUCS Print<br>1111111<br>5: 2011<br>1111111<br>2222222<br>3: blablabla<br>Not Found<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">//#include &quot;vector&quot;</span><br><span class="line">#include &quot;set&quot;</span><br><span class="line">#include &quot;map&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">//typedef long long LL;</span><br><span class="line"></span><br><span class="line">//5个map变量分别建立书名、作者、关键词、出版社及出版年份与id的映射关系</span><br><span class="line">map&lt;string, set&lt;int&gt;&gt; mpTitle, mpAuthor, mpKey, mpPub, mpYear;</span><br><span class="line"></span><br><span class="line">void query(map&lt;string,set&lt;int&gt;&gt; &amp;mp, string&amp; str)&#123;//在mp中查找str</span><br><span class="line">    if(mp.find(str) == mp.end()) printf(&quot;Not Found\n&quot;);//找不到</span><br><span class="line">    else&#123;</span><br><span class="line">        //找到</span><br><span class="line">        for (set&lt;int&gt;::iterator it = mp[str].begin(); it != mp[str].end(); it++) &#123;</span><br><span class="line">            printf(&quot;%07d\n&quot;, *it);//输出str对应的所有id</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, m, id, type;</span><br><span class="line">    string title, author, key, pub, year;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);//书的数目</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d%*c&quot;, &amp;id);</span><br><span class="line">        getline(cin, title);//书名</span><br><span class="line">        mpTitle[title].insert(id);//把id加入title对应的集合中</span><br><span class="line">        getline(cin, author);//读入</span><br><span class="line">        mpAuthor[author].insert(id);//把id加入author对应的集合中</span><br><span class="line">        while (cin &gt;&gt; key) &#123;//每次读入一个关键词key</span><br><span class="line">            mpKey[key].insert(id);//把id加入key对应的集合中</span><br><span class="line">            int c = getchar();//接受关键字key后的字符</span><br><span class="line">            if (c == &apos;\n&apos;) &#123;//如果是换行，说明关键字输入结束</span><br><span class="line">                break;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        getline(cin, pub);//出版社pub</span><br><span class="line">        mpPub[pub].insert(id);//把id加入pub对应的集合中</span><br><span class="line">        getline(cin,year);//出版日期year</span><br><span class="line">        mpYear[year].insert(id);//把id加入year对应的集合中</span><br><span class="line">    &#125;</span><br><span class="line">    string temp;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;m);//查询次数</span><br><span class="line">    for (int i = 0 ; i &lt; m; i++) &#123;</span><br><span class="line">        scanf(&quot;%d: &quot;, &amp;type);//查询类型</span><br><span class="line">        getline(cin,temp);//欲查询的字符串</span><br><span class="line">        cout &lt;&lt; type &lt;&lt; &quot;: &quot; &lt;&lt; temp &lt;&lt; endl;//输出类型和字符串</span><br><span class="line">        if (type == 1) &#123;</span><br><span class="line">            query(mpTitle, temp);</span><br><span class="line">        &#125;else if (type == 2) &#123;</span><br><span class="line">            query(mpAuthor, temp);</span><br><span class="line">        &#125;else if (type == 3) &#123;</span><br><span class="line">            query(mpKey, temp);</span><br><span class="line">        &#125;else if (type == 4) &#123;</span><br><span class="line">            query(mpPub, temp);</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            query(mpYear, temp);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>介绍map&lt;string,set<int>&gt;用法：<br>set元素插入采用的是insert函数，因此mp[“Name”].insert(id);<br>遍历问题：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">for(set&lt;int&gt;::iterator it = mp[&quot;Mike&quot;].begin(); it != mp[&quot;Mike&quot;].end() ; it++)&#123;</span><br><span class="line">    printf(&quot;%d\n&quot;, *it);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></int></p>
<p>其他的如书名，作者，出版社及出版日期可以作为整体读入<br>关键词读入的问题：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">while(cin &gt;&gt; key)&#123;</span><br><span class="line">    mpKey[key].insert(id);</span><br><span class="line">    char c = getchar();//读入一个词后的字符</span><br><span class="line">    if(c == &apos;\n&apos;) break;//如果是换行，跳出</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <a class="extend prev" rel="prev" href="/page/8/"><i class="fa fa-angle-left"></i></a><a class="page-number" href="/">1</a><span class="space">&hellip;</span><a class="page-number" href="/page/8/">8</a><span class="page-number current">9</span><a class="page-number" href="/page/10/">10</a><span class="space">&hellip;</span><a class="page-number" href="/page/21/">21</a><a class="extend next" rel="next" href="/page/10/"><i class="fa fa-angle-right"></i></a>
  </nav>



          </div>
          


          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/images/avatar.jpg" alt="何米酥">
            
              <p class="site-author-name" itemprop="name">何米酥</p>
              <p class="site-description motion-element" itemprop="description">Just do...</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">202</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">8</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">78</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/hemisu" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://www.zhihu.com/people/hemisu" target="_blank" title="知乎">
                      
                        <i class="fa fa-fw fa-globe"></i>知乎</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      

      
        <div class="back-to-top">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2015 &mdash; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">何米酥</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>




        







        
      </div>
    </footer>

    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  

  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
</html>
